# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2021/5/4 14:01
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : continuous_subsequence_max_sum.py
@Version     : Version 1.0.0
@Description : TODO 动态规划实现时间复杂度O(n)的算法求解连续子序列和最大值问题
@Created By  : PyCharm
"""


def bottom_up_cont_sub_seq(seq):
    """
    自底向上实现时间复杂度O(n)的算法求解连续子序列和最大值
    :param seq:原始序列
    :return: 连续子序列和最大值，连续子序列和最优解
    """
    item_nums = len(seq)
    table = [0] * (item_nums + 1)  # 初始化动态规划表
    table[1] = seq[0]  # 表中第2项为序列第1项
    global_best = []  # 初始化最优解序列
    for i in range(2, item_nums + 1):
        table[i] = max(table[i - 1] + seq[i - 1], seq[i - 1])  # 由于表长比序列大1，所以当前元素索引为i-1
    max_sum = max(table)
    ind_max = table.index(max_sum)
    while ind_max >= 1:
        # 表当前元素值等于表左边子问题的值+序列当前元素值(索引比表小1)
        if table[ind_max] == table[ind_max - 1] + seq[ind_max - 1]:
            global_best.append(seq[ind_max - 1])
            ind_max -= 1
        # 达到起点终止
        else:
            global_best.append(seq[ind_max - 1])
            break
    return max_sum, global_best[::-1]


if __name__ == '__main__':
    sequence = [-2, 11, -4, 13, -5, 2]
    max_value,global_best_sub_seq = bottom_up_cont_sub_seq(sequence)
    print("原始序列为:{}\n连续子序列和最大值为:{}\n连续子序列和最优解为:{}".format(sequence,max_value,global_best_sub_seq))
